/***************************************************
*	FileName    :	eightPuzzle.h
*	Description :	
*	Created		:	
*   Compiler	:	g++ -o eightPuzzle -g eightPuzzle.h eightPuzzle.cpp main.cpp	
*	
*	Author		:	Victor, mcvector.gu@gmail.com
*	Company		:	College of Information Technology and Science, Chengdu University Of Technology
******************************************************/
#ifndef EIGHTPUZZLEV2
#define EIGHTPUZZLEV2
#include<iostream>
#include<vector>
#include<stack>
#include<stdlib.h>
using namespace std;
//priority queue

//the first element of vector is the top element
class StateNode;
class PrioQueue
{
private:
	vector<StateNode*> node;
	//put the top at the end of the vector
public:
	void push(StateNode* in);	//push an StateNode in to queue
	void pop();
	StateNode* top()			//return the top element of queue
	{
		if(node.empty())
		{
			cout<<"PrioQueue is empty\n";
			exit(0);
		}
		return node[0];
	}
	StateNode* at(int i)			//return the ith element
	{
		return node[i];
	}
	int size()						//return the size of the element
	{
		return node.size();
	}
	bool isEmpty()
	{
		return node.empty();
	}
};

//StateNode
class StateNode
{
	friend class StateTree;
	friend class PrioQueue;
    friend bool operator<=(StateNode left, StateNode right)
    {
        return left.manhatten <= right.manhatten;
    }
	friend ostream& operator<<(ostream &out, const StateNode& right)
	{
		out<<right.state[0][0]<<"  "<<right.state[0][1]<<"  "<<right.state[0][2]<<endl
			<<right.state[1][0]<<"  "<<right.state[1][1]<<"  "<<right.state[1][2]<<endl
			<<right.state[2][0]<<"  "<<right.state[2][1]<<"  "<<right.state[2][2]<<endl;
	}
private:
    vector< vector<int> > state;        //save the state in a 2D vector
    StateNode *father;                  //save a pointer to it's father
    int bCal,bRow;                      //save cal and row of blank
    int step;                           //how many steps have been taken to reach this state
    int manhatten;                      //manhatten
public:
    StateNode(vector< vector<int> > vState, StateNode* f = NULL, int stp = 0)
    {
        state = vState;
        father = f;
        step = stp;
    }
	bool isSameAs(StateNode* anotherState)const
	{
		if(this->state == anotherState->state)
		  return true;
		else
		  return false;
	}

};

class StateTree
{
private:
	static const int BLANK = 0;	//define blank to 0
	bool done;
	PrioQueue open;			//an open list store in an priority queue
	vector<StateNode*> close;	//close
	StateNode* startState;		//startState
	StateNode* goalState;		//goalState
	stack<StateNode*> solution; //store the solution
	int goalStateType;
	void creatGoalState();		//come up with a goalState based on startState
	//move to four directions
	StateNode* moveUp(StateNode* preState);
	StateNode* moveDown(StateNode* preState);
	StateNode* moveLeft(StateNode* preState);
	StateNode* moveRight(StateNode* preState);
	void getManhattenAndCalRow(StateNode* st);	//creat Manhatten, call by constructor, also 
public:
	StateTree(vector< vector<int> > initial); //creat a tree by StateTree
	~StateTree()
	{
		for(int i=0; i<open.size(); i++)
		  delete open.at(i);
		for(int i=0; i<close.size(); i++)
		  delete close.at(i);
	}
	void creatChildren();	//creat children from preState
	void solve();							//solve the puzzle and put the result into a stack
	void showResult();						//print result
	void showGoalState()		//debug
	{
		cout<<*goalState;
	}
};




#endif
